A typical data storage system includes a cache device (herein simply referred to as a cache) that stores data so that future requests for that data can be served faster. The data that is stored within a cache might be values that have been computed earlier or duplicates of original values that are stored elsewhere. If the requested data is contained in the cache (herein referred to as a cache hit), this request can be served by simply reading the cache, which is comparatively faster. On the other hand, if the requested data is not contained in the cache (herein referred to as a cache miss), the data has to be recomputed or fetched from its original storage location, which is comparatively slower. Hence, the greater the number of requests that can be served from the cache, the faster the overall system performance becomes.
Caches can have high churn (i.e., many overwrites) as they try to keep the hottest (i.e., most relevant) data available in a limited storage area. This becomes a problem when the media (e.g., solid state drive (SSD), hard disk drive (HDD), etc.) used for the cache has limited overwrites before the device fails. One conventional approach to address this problem is to pack cached blocks together into larger units that are written to and evicted from the cache as a group. This eliminates small overwrites and reduces overwrites in general. Such a conventional approach, however, can cause fragmentation in the cache and wasted space.
Ideally, blocks of data should be packed together in larger units such that they will all age out at the same time, and the group is evicted together, thus limiting fragmentation. Conventionally, data blocks are packed together based on temporal or stream locality. Packing data blocks using these criteria, however, are problematic. First, blocks which arrive at the same time may contain disparate and unrelated data which do not necessarily expire (in terms of cache utility) at the same time. Second, per-stream packing typically requires that a partially packed group be held in memory for each stream until it can be filled and written to the cache. For example, if there are 500 streams and the packing size is 1 megabyte (MB), the system must allocate 500 MB of memory just for the partially packed, per-stream groups.